package com.gzl.exercise;

import org.junit.jupiter.api.Test;

import java.util.Arrays;

/**
 * @PROJECT_NAME: exercise
 * @NAME: 计算总数
 * @DESCRIPTION:
 * @USER: gaozengliang
 * @DATE: 2023/10/25
 */
public class 计算总数 {

    /**
     *某种病毒具有很强的繁殖能力，从病毒粒子出生后的第5分钟开始，每分钟可以复制出一个新的病毒粒子。
     * 新出生的病毒粒子从第5分钟开始，也可以每分钟复制一个新的病毒粒子
     *
     * 举例来说，第1分钟时有一个病毒粒子，此病毒粒子从第5分钟开始复制新的病毒粒子，
     * 因此第5分钟时的病毒数量为2个，第6分钟时又复制出新的病毒粒子，因此第6分钟的病毒数量为3个，
     * 以此类推，第7分钟时病毒粒子数为4;第8分钟时病毒粒子数为5;
     * 第9分钟时，第5分钟复制出的病责粒子开始复制新的病毒粒子，因此第9分钟时的病毒总数为7;
     * 第10分钟时，第6分钟复制出的病毒粒子开始复制新的病毒粒子，因此第10分钟时的病毒粒子总数为10。
     *
     * 题目描述:
     * 计算病毒粒子总数，已知第一分钟时出生了一个病毒粒子，假设所有病毒粒子不会自动死亡
     * 蓝桥杯青少年创意编程大赛
     * 请计算第N分钟时的病毒粒子总数。
     * 例如:前10分钟病毒粒子的总数分别为1,1,1,1,2,3,4,5,7,10
     * */
    @Test
    void calcSum(){
        int n = 10;
        if (n<5){
            System.out.println(1);
            return;
        }
        int num[] = new int[n+2];
        for (int i=1;i<5;i++){
            num[i] = 1;
            System.out.print(num[i]+",");
        }
        for (int i=5;i<=n;i++){
            num[i] = num[i-1] + num[i-4];
            System.out.print(num[i]+",");
        }
    }

    /**
     * 第五题(难度系数5，满分 35 分)
     * 编程实现:最佳策略
     * 题目描述:
     * 有一辆最大载重为15 吨的货车。现一共有五件货品，重量分别是 W1,W2,W3,W4,W5，价值分别是 V1,V2,V3,V4,V5。
     * 现希望货车中装入的货物总价值越大越好。请你编写程序，帮助计算，在不超载的情况下，货车能够运输的货品最大总价值是多少?
     * 例如，5 件货品的重量和价值如下表所示:
     * 重量3吨4吨6吨6吨5吨，价值1000元500元400元1200元300元
     * 输入描述:第一行输入5个正整数，数字之间以一个空格分隔，表示货品的重量，第二行输入5个正整数，数字之间以一个空格分隔，表示货品的价值.
     * 输出描述:计算能够运输的货品最大总价值，并输出。
     * 样例输入:3 4 6 6 5
     * 1000 500 400 1200 300
     * 样例输出:2700；
     * */
    @Test
    void test01(){
        int MAX_W = 15;
        int tempW = 0;
        int MaxV = 0;
//        int[] w = {3, 4, 6, 6, 5};
//        int[] v = {1000, 500, 400, 1200, 300};
        int[] w = {3,4,6,6,5,2};
        int[] v = {1000,500,400,1200,600,100};
        int[] wt = new int[w.length+1];


        for (int i=0;i<w.length;i++){
            // 计算权重
            wt[i] = v[i]/w[i];
//            System.out.println(wt[i]);
        }
        // 拷贝数组
        int[] sortw = Arrays.copyOf(wt, wt.length);
        // 排序
        for (int i=0;i<w.length;i++){
            for (int j=i+1;j<w.length-1;j++){
                if (sortw[i]<sortw[j]){
                    int temp = sortw[i];
                    sortw[i] = sortw[j];
                    sortw[j] = temp;
                }
            }
        }

        // 检验排序
        for (int i=0;i<w.length;i++){
            System.out.print(wt[i]+",");
        }

        // 根据权重装车
        for (int i=0;i<w.length;i++){
            for (int j=0;j<w.length;j++){
                // 找出对应重量
                if (sortw[i]==wt[j]){
                    // 重量不超过最大载重
                    if (w[j]<=MAX_W && tempW+w[j]<=MAX_W){
                        tempW += w[j];
                        MaxV += v[j];
                    }
                }
            }
        }
        System.out.println("最大价值为："+MaxV);
    }

    @Test
    void test02(){
        final int W = 15;
        int[] weights = {3,4,6,6,5,2};
        int[] values = {1000,500,400,1200,300,100};
        int n = weights.length;
        int[][] dp = new int[n+1][W+1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= W; j++) {
                if (j >= weights[i - 1]) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        System.out.println(dp[n][W]);


        /*int[] dp = new int[W + 1];

        for (int i = 0; i < n; i++) {
            for (int j = W; j >= weights[i]; j--) {
                System.out.println(j +","+ dp[j] +","+ (j-weights[i]) +","+ dp[j-weights[i]] +","+ (dp[j - weights[i]] + values[i]));
                dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
            }
            System.out.println();
        }

        System.out.println(dp[W]);*/
    }


}
